import time
from generator import generate_random_array, generate_nearly_sorted_array, generate_reversed_array
from alg import SORT_ALGORITHMS

def test_sorting_algorithm(sort_func, arr):
    """
    测试排序算法的性能
    :param sort_func: 排序函数
    :param arr: 待排序数组
    :return: 排序时间（秒）
    """
    arr_copy = arr.copy()
    start_time = time.time()
    sorted_arr = sort_func(arr_copy)
    end_time = time.time()
    
    # 验证排序结果
    assert sorted_arr == sorted(arr), f"{sort_func.__name__} 排序结果错误"
    
    return end_time - start_time

def run_tests():
    """
    运行所有测试用例
    """
    sizes = [1000, 10000, 100000]
    algorithms = [
        ('插入排序', SORT_ALGORITHMS['insertion_sort']),
        ('冒泡排序', SORT_ALGORITHMS['bubble_sort']),
        ('快速排序', SORT_ALGORITHMS['quick_sort']),
        ('堆排序', SORT_ALGORITHMS['heap_sort']),
        ('归并排序', SORT_ALGORITHMS['merge_sort']),
        ('希尔排序', SORT_ALGORITHMS['shell_sort'])
    ]
    
    results = []
    
    for size in sizes:
        print(f"\n测试数组大小: {size}")
        
        # 生成测试数据
        random_arr = generate_random_array(size)
        nearly_sorted_arr = generate_nearly_sorted_array(size, int(size * 0.1))
        reversed_arr = generate_reversed_array(size)
        
        test_cases = [
            ('随机数组', random_arr),
            ('接近有序数组', nearly_sorted_arr),
            ('逆序数组', reversed_arr)
        ]
        
        for alg_name, sort_func in algorithms:
            print(f"\n{alg_name}:")
            for case_name, arr in test_cases:
                try:
                    time_taken = test_sorting_algorithm(sort_func, arr)
                    results.append({
                        'algorithm': alg_name,
                        'size': size,
                        'case': case_name,
                        'time': time_taken
                    })
                    print(f"  {case_name}: {time_taken:.4f} 秒")
                except Exception as e:
                    print(f"  {case_name}: 失败 - {str(e)}")
    
    return results

if __name__ == "__main__":
    results = run_tests() 